//
// Created by Symps on 2025/11/15.
//

#include <algorithm>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

string removeDuplicates(string s) {
    std::stack<char> st;
    for (char ch : s) {
        if (st.empty()) {
            st.push(ch);
        } else {
            if (st.top() == ch) {
                st.pop();
            } else {
                st.push(ch);
            }
        }
    }
    string ret;
    while (!st.empty()) {
        ret += st.top();
        st.pop();
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
}

void test1() {
    string s = "abbaca";
    cout << removeDuplicates(s) << endl;
}

bool backspaceCompare(string s, string t) {
    string st1;
    string st2;
    for (char& ch : s) {
        if (ch == '#' && !st1.empty()) {
            st1.pop_back();
        } else if (ch != '#') {
            st1 += ch;
        }
    }

    for (char& ch : t) {
        if (ch == '#' && !st2.empty()) {
            st2.pop_back();
        } else if (ch != '#') {
            st2 += ch;
        }
    }
    return st1 == st2;
}

void test2() {
    string s = "y#fo##f";
    string t = "y#f#o##f";
    cout << backspaceCompare(s, t) << endl;
}

int calculate(const string& s) {
    stack<int> st;
    char sign('+');
    int i{};
    while (i < s.size()) {
        char ch(s[i]);
        if (ch == ' ') {
            ++i;
            continue;
        }
        string num("0");
        while (ch >= '0' && ch <= '9') {
            num += ch;
            ch = s[++i];
        }

        if (sign == '+') {
            st.push(stoi(num));
        } else if (sign == '-') {
            st.push(-stoi(num));
        } else if (sign == '*') {
            st.top() *= stoi(num);
        } else if (sign == '/') {
            st.top() /= stoi(num);
        }
        sign = ch;
        ++i;
    }

    int ret = 0;
    while (!st.empty()) {
        ret += st.top();
        st.pop();
    }
    return ret;
}

void test3() {
    // string s = " 42 ";
    // string s(" 3/2 ");
    string s = " 3+5 / 2 ";
    cout << calculate(s) << endl;
}

string decodeString1(string s) {
    int i{};
    stack<int> st_num;
    stack<int> st_bracket;

    while (i < s.size()) {
        if (s[i] >= '0' && s[i] <= '9') {
            string num{"0"};
            while (s[i] >= '0' && s[i] <= '9') {
                num += s[i++];
            }
            st_num.push(stoi(num));
            continue;
        }
        if (s[i] == '[') {
            st_bracket.push(i + 1);
            ++i;
        } else if (s[i] == ']') {
            string sub_str;
            int times(st_num.top());
            st_num.pop();
            int subBegin(st_bracket.top());
            st_bracket.pop();
            string single = s.substr(subBegin, i - subBegin);
            int numLen = to_string(times).size();
            while (times--) {
                sub_str += single;
            }
            s.replace(subBegin - 1 - numLen, (i + 1) - (subBegin - 1 - numLen), sub_str);
            i = subBegin - 1 - numLen - single.size() + sub_str.size();
        } else {
            while (s[i] >= 'a' && s[i] <= 'z') {
                ++i;
            }
        }
    }
    return s;
}

string decodeString(string s) {
    stack<int> timess;
    stack<string> words;
    int i{};
    while (i < s.size()) {
        if (isdigit(s[i])) {
            string num{"0"};
            while (isdigit(s[i])) {
                num += s[i++];
            }
            timess.push(stoi(num));
            continue;
        }

        if (s[i] == '[') {
            ++i;
            string word;
            while (isalpha(s[i])) {
                word += s[i++];
            }
            words.push(word);
            continue;
        }

        if (s[i] == ']') {
            int times(timess.top());
            timess.pop();
            string word(words.top());
            words.pop();

            string temp;
            while (times-- > 0) {
                temp += word;
            }
            if (!words.empty()) {
                words.top() += temp;
            } else {
                words.push(temp);
            }
            ++i;
        }

        if (words.empty()) {
            words.emplace("");
        }
        while (isalpha(s[i])) {
            words.top() += s[i++];
        }
    }
    return words.top();
}

void test4() {
    string strs[] = {
        // "3[a]2[bc]",
        // "2[ab]ef",
        // "3[a2[c]]",
        // "2[abc]3[cd]ef",
        // "abc3[cd]xyz",
        // "100[leetcode]"
        // "3[z]2[2[y]pq4[2[jk]e1[f]]]ef"
        "abc3[cd]xyz"
    };
    for (string& str : strs) {
        cout << str << ": " << decodeString(str) << endl;
    }
}

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> st;
    int i{};
    size_t sz2 = popped.size();
    for (int& x : pushed) {
        st.push(x);
        while (st.size() && st.top() == popped[i]) {
            st.pop();
            ++i;
        }
    }
    return i == sz2;
}

void test5() {
    vector<int> pushed{1, 2, 3, 4, 5}, popped{4, 5, 3, 2, 1};
    pushed = {1, 2, 3, 4, 5}, popped = {4, 3, 5, 1, 2};
    cout << validateStackSequences(pushed, popped) << endl;
}

int main() {
    // test1();
    // test2();
    // test3();
    // test4();
    test5();
    return 0;
}
